//
// Created by liushuai on 2020/5/5.
//
#include <vector>
#include "dfs_tree.h"
void dfs_tree_rec(TreeNode*root){

}
void dfs_tree_stack(TreeNode*root){
    std::stack<TreeNode*> s;
    TreeNode* current_node = root;
    s.push(root);
    while (current_node){
        TreeNode* pop_node = current_node;
        if(s.size()>0)
            s.pop();
        std::cout<<"访问节点:"<<pop_node->val;
        if(pop_node->right)
            s.push(pop_node->right);
        if(pop_node->left)
            s.push(pop_node->left);
        if(s.size()>0)
            current_node = s.top();
        else
            current_node = nullptr;
    }
}

void dfs_travel_layer(TreeNode*root,int layer,std::vector<std::vector<int>>& result){
    if(root){
        // 不能直接push_back，通过判断result的大小获取层数否则层result的size可能会大于层数
        if(result.size()<layer+1)
            result.push_back(std::vector<int>());
        result.at(layer).push_back(root->val);
        dfs_travel_layer(root->left,layer+1,result);
        dfs_travel_layer(root->right,layer+1,result);
    }
}
std::vector<std::vector<int>> dfs_travel_layer(TreeNode* root){
    std::vector<std::vector<int>> result;
    dfs_travel_layer(root,0,result);
    return result;
}
int maxDepth(TreeNode* root){
    if(!root)
        return 0;
    else{
        int left_size = maxDepth(root->left)+1;
        int right_size = maxDepth(root->right)+1;
        int result = left_size>right_size?left_size:right_size;
        return result;
    }
}

